\section{Descripción del Problema}
Se debe desarrollar un algoritmo para un módulo de diseño CAD 2D el cual debe tomar como entrada perfiles de edificios y como salida debe retornar el perfil de todos los edificios juntos sin sus intersecciones.
La entrada se compone de una línea indicando la cantidad de edificios y a continuación una línea por cada uno de estos, indicando la posición del lado izquierdo, la altura y la posición del lado derecho.
La salida es una secuencia de posiciones x(horizonte) e y(altura) que representan el perfil resultante.

\subsection{Ejemplo}
Entrada, siete edificios.
\begin{verbatim}
7
4 15 10
2 11 9
7 7 18
12 13 16
20 9 28
22 20 25
26 13 29
\end{verbatim}
Salida, perfil conjunto:
\begin{verbatim}
2 11 4 15 10 7 12 13 16 7 18 0 20 9 22 20 25 9 26 13 29 0
\end{verbatim}
Este ejemplo se representa gráficamente en la figura \ref{fig:ej2:ejemplo}

\ponerGrafico{imagenes/ejemplo_ej2.pdf}{Entrada(izquierda) y salida(derecha) del ejemplo citado}{1}{ej2:ejemplo}

\section{Idea General de la Resolución}los
La idea detrás del algoritmo es desglosar cada edificio en un \textit{flanco de subida}, lado izquierdo y un \textit{flanco de bajada} lado derecho, recorrer estos en forma ordenada e ir generando la traza del perfil con las coordenadas $x_{i+1}>x_{i}$ e $y_{i}$.

En la figura \ref{fig:ej2:flancos}, se identifican los flancos.
La solución está compuesta por coordenadas pertenecientes a flancos de subida o intersecciones entre uno de bajada y el nivel de altura del edificio\footnote{El nivel de altura de un edificio es la componente $y$ de los flancos de subida y de bajada que lo componen.} inmediatamente menor que el actual.

\ponerGrafico{imagenes/flancos_ej2.pdf}{Identificación de flancos}{1.3}{ej2:flancos}

\subsection{Glosario}
A continuación se aclaran los términos usados en la explicación de la solución:
\begin{itemize}
\item \textbf{Flanco de subida:} Corresponde a la transición desde el horizonte($y=0$) hasta la altura de un edificio. Su componente $x$ representa el lado izquierdo del mismo.
\item \textbf{Flanco de bajada:} Corresponde a la transición desde la altura de un edificio  hasta el horizonte($y=0$). Su componente $x$ representa el lado derecho del mismo.
\item \textbf{Edificio vigente:} Cuando se halla un flanco de subida, se considera que el edificio que lo representa está \textit{vigente}, esto quiere decir que hasta que no se encuentre el flanco de bajada del mismo, la altura mínima que se alcanzará no será menor a la del edificio en cuestión.
\item \textbf{Edificio actual:} Es el que contiene la altura máxima local y está en vigencia.
\end{itemize}

\subsection{Casos}
Al analizar el problema desde este punto de vista, nos encontramos con cuatro casos principales:
	
\begin{itemize}
\item[1] \textbf{Flanco de subida con altura máxima}
En este caso, la coordenada es considerada parte de la solución y el edificio actual es el que la contiene.
\item[2] \textbf{Flanco de subida con altura menor al edificio actual}
Si existe un edificio actual con altura superior a la del flanco, la coordenada de este no será solución pero se agregará su altura a una estructura ordenada hasta que se encuentre el flanco de bajada correspondiente al edificio en cuestión.
\item[3] \textbf{Flanco de bajada con altura menor al edificio actual}
Ante un flanco con estas características, solo se extrae su altura de la estructura ordenada. El edificio que lo contiene deja de estar vigente.
\item[4] \textbf{Flanco de bajada del edificio actual}
Este corresponde al flanco que mantiene la altura máxima(local). En este caso su coordenada $x$ será solución parcial. Este edificio deja de estar vigente y el siguiente edificio actual será el inmediatamente menor\footnote{Ante un flanco de bajada el edificio deja de estar vigente y de ser el actual, el próximo actual es el que se encuentra en la estructura ordenada con altura máxima.}. Su altura será parte de la solución parcial.
\end{itemize}

Evaluando flanco a flanco en la figura \ref{fig:ej2:flancos}, vemos que:
\begin{itemize}

\item A1 es solución y A, edificio actual(caso 1). 
\item Luego B1 es solución y pasa a ser el nuevo edificio actual, notar que A sigue estando en vigencia(caso 1). 
\item C1 no pertenece a la solución por tener altura menor al edificio actual pero C, entra en vigencia(caso 2). 
\item A2 no es solución y A deja de estar en vigencia(caso 3).
\item La componente $x$ de B2 es solución, B deja de estar en vigencia y de ser el edificio actual. El siguiente actual es C, que estaba en vigencia, su coordenada $y$ se incluye en la solución(caso 4).
\item D1 es solución y D edificio actual(caso 1).
\item La componente $x$ de D2 es solución, D deja de estar en vigencia y de ser el edificio actual. El siguiente actual es C, que estaba en vigencia, su coordenada $y$ se incluye en la solución(caso 4).
\item Finalmente, la componente $x$ de C2 es solución, C deja de ser edificio actual y de estar en vigencia. Al no haber mas edificios que analizar, se añade el $y=0$ y se termina(caso 4).
\end{itemize}

\section{Pseudocódigo}

\begin{algorithm}[H]
\KwData{Arreglo de flancos}
	
	ordenar(flancos)

	Edificio edificioActual (flancos[0].altura,flancos[0].idEdificio)
	
	SolucionParcial solCandidata(flancos[0].x,flancos[0].altura)
	
	PilaOrdenada alturas

	\tcp{Agrego el piso como una altura}
	alturas.push(Edificio(0,-1))
	
	\ForAll {flanco en flancos-flanco[0]}{	
		\tcp{Caso 4}
		\If{flanco.idEdificio == edificioActual.idEdificio}{	
			\If{edificioActual.altura != alturas.top().altura}{			
				solucion.agregar(solCandidata.x)
				
				solucion.agregar(solCandidata.y)				
				
				solCandidata.x = flanco.x
				
				solCandidata.y = alturas.top().altura
			}			
			edificioActual = alturas.pop()
		}\ElseIf{flanco.subida}{
			\tcp{Caso 1}
			\If{flanco.altura $>$ edificioActual.altura}{
				\If{flanco.x != solCandidata.x}{
					solucion.agregar(solCandidata.x)
					
					solucion.agregar(solCandidata.y)
				}	
				solCandidata.x = flanco.x
				
				solCandidata.y = flanco.altura
				
							
				alturas.push(edificioActual)
								
				edificioActual.altura = flanco.altura
				
				edificioActual.idEdificio = flanco.idEdificio
			}
			\tcp{caso 2}
			\Else{
				alturas.push(Edificio(flanco.altura,flanco.idEdificio))
			}
		
		}\tcp{caso 3}
		\Else{
			alturas.erase(flanco.idEdificio);
		}		
	}
	solucion.agregar(solCandidata.x)
		
	solucion.agregar(solCandidata.y)
	
	\Return solucion

\caption{Perfiles}
\label{alg:ej2}
\end{algorithm}

\section{Correctitud y Complejidad}

\subsection{Correctitud}

La solución cumple con las siguientes condiciones
Sea $S$ la solución del problema, de la forma:
$$
S = \{x_{0},y_{0},...x_{k},y_{k},...x_{n},0\}
$$
Siendo $x$ la posición de algún lado del edificio e $y$ la altura de alguno de estos, se puede ver en el pseudocódigo(\ref{alg:ej2}), en las líneas 9,10,17,18,29 y 29 que la solución generada cumple con el orden alternado de componente $x$ e $y$. Dado que en la línea 5 se agrega la altura del horizonte, al finalizar, la última coordenada $y$ será 0.
También se cumple que:
$$
\forall x ; x \in S ; x_{i+1}>x_{i} 
$$
Dado que se recorre el arreglo de flancos de forma ordenada, de acuerdo a la posición $x$, la salida del algoritmo cumple la condición.

$y_i$ es la altura máxima de los edificios que están vigentes. Cuando se encuentra un flanco de subida, si su altura es mayor a la altura del edificio actual, se agrega a la solución(línea 19 y 20). Cuando se encuentra el flanco de bajada del edificio actual, la componente $x$ del mismo se agrega a la solución(línea 11) y la componente $y$ es la que se encuentra en el tope de la pila ordenada(línea 12). Cuando un edificio entra en vigencia su altura se agrega a la pila ordenada(línea 21 y 25) y cuando deja de estarlo se saca de la misma(línea 13 y 27). Dado que la estructura donde se guardan las alturas de edificios está ordenada, siempre sacamos la altura máxima.
Para evitar problemas con flancos en la misma posición $x$, al encontrar una solución, la misma se guarda como "candidata" y se analiza el flanco siguiente, si tiene distinto valor de $x$ se agrega la solución candidata a la solución final.

Finalmente, el algoritmo termina cuando acaba de recorrer todos los flancos(línea 6).

\subsection{Complejidad}
La complejidad del algoritmo dado es de $O(nlog(n))$ que esta dado por el ordenamiento de la entrada y despues se recorre una sola vez para procesarla. \\
\subsection{Test de Performance}
Como se puede ver en el gr\'afico, el cual fue generado con entradas aleatorias para cada N al cual se iba a evaluar (se generaban N edificios con coordenadas aleatorias pero consistentes, der > izq) y despues se corr\'ia 200 veces para mitigar el error que pudiera generarse en el computador. \\
\\
\includegraphics[scale=0.8]{imagenes/ej2.png} 
\\
El gr\'afico resultante tiene un trazado $nlog(n)$ en funci\'on del tiempo y aproximadamente alcanzara el segundo de duraci\'on en el N 173000. De esto podemos tomar una cota superior de $\frac{1}{173000}$, lo interesante en este ejercicio es que tambien puedo tomar una cota inferior y que tambien se aproxima a una funci\'on $nlog(n)$ en este caso con una pendiente de $\frac{1}{62500}$. Ademas se observa que por m\'as que el tiempo promedio crece de forma logaritmica lo hace tan lentamente que la pendiente resultante es tan baja que tiende a parecerse a una lineal, esto tiene que ver con que si la instanc\'ia tarda poco en ser ordenada el algoritmo es casi lineal. Como contraparte tambien se puede observar casos en los que les costo ordenar y genera los picos en el dibujo formando una funci\'on $nlog(n)$ mucho m\'as fuerte la cual genera una cota superior bastante clara. \\